package Test;

public class MylinkedList {


    static class ListNode {
        public int val;
        public ListNode prev;//前驱
        public ListNode next;//后继

        public ListNode(int val) {
            this.val = val;
        }
    }

        public ListNode head;
        public ListNode last;


        /*public void creatList() {
            MySingleList.ListNode listNode1 = new MySingleList.ListNode(11);
            MySingleList.ListNode listNode2 = new MySingleList.ListNode(12);
            MySingleList.ListNode listNode3 = new MySingleList.ListNode(13);
            MySingleList.ListNode listNode4 = new MySingleList.ListNode(14);

        }*/

        /**
         * 头插法
         * 定义一个node , 如果头结点为空时,前驱和后继都是node
         * 不为空时,将node的next给head, head的前驱给node, 再将head给node
         * @param data
         */
        public void addFirst(int data){
            ListNode node = new ListNode(data);
            if (head == null) {
                head = node;
                last = node;
            }else {
                node.next = head;
                head.prev = node;
                head = node;
            }
        }

        /**
         * 尾插法
         * 如果头结点为空,将head和last都给node(直接插入)
         * 否则 ,将last.next 给node, node.prev给last,再将node变为last
         * @param data
         */
        public void addLast(int data){
            ListNode node = new ListNode(data);
            if (head == null) {
                head = node;
                last = node;
            }else {
                last.next = node;
                node.prev = last;
                last = node;
            }
        }

        /**任意位置插入,第一个数据节点为0号下标
         * 1.当插入位置不合法时 , 抛出异常
         * 2.当插入位置为头结点时 , 采用头插法 ;当插入位置为尾节点时 , 采用尾插法
         * 3.定义cur表示要插入的位置 遍历链表 ,链表中间插入元素 要改四个元素
         *   1)将插入元素 node 的后继改为cur
         *   2)将cur前一个节点的后继改为 node
         *   3)将node 的前驱改为cur 的前驱
         *   4)将cur 的前驱改为node
         * @param index
         * @param data
         * @return
         */
        public void addIndex(int index,int data){
            if(index < 0 || index > size()) {
                throw new ListIndexOutOfException();
            }
            if(index == 0) {
                addFirst(data);
                return;
            }
            if(index == size()) {
                addLast(data);
                return;
            }

            ListNode cur = findIndex(index);
            //
            ListNode node = new ListNode(data);
            node.next = cur;
            cur.prev.next = node;
            node.prev = cur.prev;
            cur.prev = node;

        }
        private ListNode findIndex(int index) {
            ListNode cur = head;
            while (index != 0) {
                cur = cur.next;
                index--;
            }
            return cur;
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
            ListNode cur = head;

            while (cur != null) {
                if (cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }

         /**删除第一次出现关键字为key的节点
        * 定义cur 代表头部遍历
        * 如果 cur 的值不等于要删除的关键字
        *      如果要删除的是头结点 :将head 向后移一位, (如果只有一个节点) 如果head不为空 ,将head的前驱置为空
        *      或者删除的是中间或者尾巴节点 :将cur 的前一个节点的后继置为cur的后继
        *                               中间节点: 如果cur的后继不为空 ,将cur后继的前驱置为cur的前驱
        *                               尾巴节点: 将last置为last的前驱
        *     返回
        * cur向后走
        * @param key
        */

        public void remove(int key){
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    //1.删除的是头结点
                    if (cur == head) {
                        head = head.next;
                        if (head != null) {
                            head.prev = null;
                        }
                    }else {
                        //删除的是 中间节点或者尾巴节点
                        cur.prev.next = cur.next;
                        //中间节点
                        if (cur.next != null) {
                            cur.next.prev = cur.prev;
                        }else {
                            //尾巴节点
                            last = last.prev;
                        }
                    }
                    return;
                }
                cur = cur.next;
            }
        }

        /**删除所有值为key的节点
        * 删除上述代码的return , 删完一次后继续删除
        * @param key
        */
        public void removeAllKey(int key){
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    //1.删除的是头结点
                    if (cur == head) {
                        head = head.next;
                        if (head != null) {
                            head.prev = null;
                        }
                    }else {
                        //删除的是 中间节点或者尾巴节点
                        cur.prev.next = cur.next;
                        //中间节点
                        if (cur.next != null) {
                            cur.next.prev = cur.prev;
                        }else {
                            //尾巴节点
                        }
                    }
                }
                cur = cur.next;
            }
        }

        /**
        * 置空链表
        * @return
        */
        public void clear() {
            ListNode cur = head;
            while (cur != null) {
                ListNode curNext = cur.next;
                cur.next = null;
                cur.prev = null;
                cur = curNext;
            }
            head = null;
            last = null;
        }
    //得到单链表的长度
        public int size() {
            ListNode cur = head;
            int len = 0;
            while (cur != null){
                len++;
                cur = cur.next;
            }
            return len;
        }

        public void display() {
            ListNode cur = head;
            while (cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
            System.out.println();
        }


}
